\documentclass[11pt]{report}
\usepackage{stylefiles/smstc_mod,stylefiles/probability,color,mathrsfs}
%\usepackage{showkeys}
%\usepackage{epsfig}
%% amsmath, amssymb, cite, fancybox, graphicx, ifthen, minitoc, url, xspace
\Streamname{Probability}  
\Unitname{Lecture} 
\Thisyear{2007/08}  
\AuthorFt{}

\theoremstyle{definition}
\newtheorem{exe}{\bf EXERCISE}
\def\N{\mathbb{N}}
\def\Z{\mathbb{Z}}
\def\Q{\mathbb{Q}}
\def\R{\mathbb{R}}
\def\C{\mathbb{C}}
\def\FF{\mathscr{F}}
\def\GG{\mathscr{G}}
\def\HH{\mathscr{H}}
\def\DD{\mathscr{D}}
\def\CC{\mathscr{C}}
\def\RR{\mathscr{R}}
\def\G{\mathbb{G}}
\def\H{\mathbb{H}}
\def\xx{\widehat{x}}
\def\XX{\widehat{X}}
\def\AA{\mathscr{A}}
\def\SS{\mathscr{S}}
\def\TT{\mathscr{T}}
\def\BB{\mathscr{B}}
\def\VV{\mathscr{V}}
\def\LL{\mathcal{L}}
\def\NN{\mathcal{N}}
\def\Qr{\mathbf{Q}}
\renewcommand{\phi}{\varphi}
\renewcommand{\epsilon}{\varepsilon}
\newcommand{\1}{{\text{\Large $\mathfrak 1$}}}
\renewcommand{\comp}{\raisebox{0.1ex}{\scriptsize $\circ$}}
\newcommand{\cadlag}{{c\`adl\`ag} }
\renewcommand{\var}{\operatorname{var}}
\newcommand{\proj}{\operatorname{proj}}
\renewcommand{\cov}{\operatorname{cov}}
\renewcommand{\limsup}{\varlimsup}
\renewcommand{\liminf}{\varliminf}
\renewcommand{\d}{\text{\rm\,d}}
\newcommand{\eqdist}{\stackrel{\text{d}}{=}}
\newcommand{\dirac}{\text{\large $\mathfrak d$}}
\newcommand{\Ri}{\Rightarrow}
\def\iid{{i.i.d.}\xspace}
\def\jid{{i.i.d.}}
\def\ie{{i.e.}\xspace}
\def\eg{{e.g.}\xspace}
%A \xrightarrow[n]{} 0
\def\bigtimes{\text{\LARGE$\times$}}
\def\xor{\text{\footnotesize$\bigtriangleup$}}
\def\prob{\operatorname{\bf prob}}
\def\no{\noindent}

%\parskip \smallskipamount
%\parindent 5mm


\begin{document} \initdoc 

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{unit}{3}{Random variables}\footnote{These notes
contain almost no proofs. For a complete set of notes, see
\cite{k}; alternatively, read the introductory book \cite{wil},
or the more advanced book \cite{fg}.}

% SYLLABUS:
% Random variables and their distributions.				DONE
% Distribution functions, probability (mass) functions, DONE
% probability density functions, 	DONE
% moments, 	DONE
% simple inequalities  (Markov, Chebychev), 	DONE
% transformations.  	DONE
% Moment generating   functions (briefly).	DONE



\section{Random variables and their distributions}

\subsection{Review of definitions}
Recall that a {\sc random variable} is a measurable function
from a measurable space $(\Omega, \FF)$ into $(\R, \BB)$.
More generally, {\sc A random element is a measurable function}
 $X$ between two measurable spaces,
an ``abstract'' one, $(\Omega, \FF)$, and a ``concrete''\footnote{
The adjectives in quotes have nothing to do with Mathematics but, rather, with
our human interpretation of it. 
}
one, $(S, \SS)$.
In other words, we require that the inverse image by $X$ of each element 
of $\SS$ be an element of $\FF$.
We denote this situation by 
\[
X : (\Omega, \FF) \to (S, \SS).
\]
For example, if
$(S, \SS) = (\R^d, \BB(\R^d))$, where $\BB(\R^d)$ are the Borel sets on $\R^d$,
we refer to $X$ as {\sc $d$ (real) random variables} or a {\sc random vector}
because we may,
by choosing Cartesian coordinates on $\R^d$, represent
$X$ by $(X_1, \ldots, X_d)$, where $X_1$ is one random variable, $X_2$ is
one random variable, ..., $X_d$ is one random variable..

\begin{exe}
\label{drill1}
Show that if $X: (\Omega, \FF) \to (S, \SS)$, $H: (S, \SS) \to (T, \TT)$
are random elements then $H \comp X$ is a random element.
\end{exe}

Recall that 
the {\sc $\sigma$-algebra generated by
a collection}, say $\AA$, of subsets of $\Omega$, is defined as
the intersection of all $\sigma$-algebras containing $\AA$; it
is denoted by $\sigma(\AA)$.
\begin{lemma}
\label{bang}
If $X : \Omega \to S$ is a function, $\FF$ a $\sigma$-algebra on $\Omega$
and $\SS$ a  $\sigma$-algebra on $S$ generated by the collection of
sets $\CC$ then $X$ is a random variable if and only if 
$X^{-1}(B) \in \FF$ for all
$B \in \CC$.
\end{lemma}
Recall that the notation
$\{X \in B\} = X^{-1}(B)$
is used all the time, so we will stick to it when we can.
\begin{corollary}
If $X: \Omega \to \R$ is a function and $\FF$ a $\sigma$-algebra on $\Omega$,
then $X$ is one random variable 
$\iff$ $\{X \le x\} \in \FF$ for all $x \in \R$
$\iff$ $\{X < x\} \in \FF$ for all $x \in \R$
$\iff$ $\{X > x\} \in \FF$ for all $x \in \R$.
\end{corollary}

%\begin{lemma}
%If $X$ is a random vector in $\R^d$ and $f: \R^d \to \R^k$ is
%a continuous function then $f \comp X$ is a random vector in $\R^k$.
%\end{lemma}

If $X_n$ is a sequence of random variables then
$X_1 + X_2, X_1 \cdot X_2, X_1 \wedge X_2$
are all random variables.
Also, recall that
$\inf_j X_j, \quad \liminf_j X_j, \sup_j X_j, \quad \limsup_j X_j$
are random variables in $\R \cup\{+\infty, -\infty\}$.

If $X: \Omega \to S$ is a function and $\SS$
a fixed $\sigma$-algebra on $S$,
the {\sc $\sigma$-algebra  generated by $X$} is defined by
\[
\sigma(X) := \{X^{-1}(B), B \in \SS\}.
\]
%It is easy to see that 
%\begin{lemma}
%(i) $\sigma(X)$ is a $\sigma$-algebra,
%(ii) $\sigma(X)$ is the intersection of all $\sigma$-algebras
%$\GG \subset \FF$ such that $X: (\Omega, \GG) \to (S, \SS)$ is 
%a random variable,
%(iii) $X$ is a random variable if and only if $\sigma(X) \subset \FF$.
%\end{lemma}
%If $Y: \Omega \mapsto S'$ is another function, and if $S'$ is endowed
%with another fixed $\sigma$-algebra $\SS'$, 
%then the notation $\sigma(X,Y)$ stands for the smallest
%$\sigma$-algebra containing $\sigma(X)= \{X^{-1}(B), B \in \SS\}$ and 
%$\sigma(Y)= \{X^{-1}(B), B \in \SS'\}$.
%\[
%\sigma(X,Y) := \sigma(\sigma(X) \cup \sigma(Y)) =: \sigma(X) \vee \sigma(Y).
%\]
%(The last bit is just another notation for the same thing.)

Let us study random elements 
in a product $S_1 \times \cdots \times S_d$ of sets.
Suppose that on each $S_i$ we have a $\sigma$-algebra $\SS_i \subset 2^{S_i}$.
We first construct a natural $\sigma$-algebra on  $S_1 \times \cdots \times S_d$.
For each $i$ consider the projection function
\[
\pi_i : S_1 \times \cdots \times S_d \to S_i; \quad
\pi_i : (s_1, \cdots, s_d) \mapsto s_i.
\]
Define 
\[
\SS_1 \otimes \cdots \otimes \SS_d := \sigma(\pi_1, \ldots, \pi_d).
\]
\begin{exe}
Consider $(S_i, \SS_i)$, $i=1, \ldots, d$. Let $d=2$ for simplicity.
Show that
\begin{align*}
\SS_1 \otimes \SS_2
&=
\sigma(
\{B_1 \times S_2: B_1 \in \SS_1\}
\cup
\{S_1 \times B_2: B_2 \in \SS_2\}).
\\
&= \sigma(\{B_1 \times B_2: B_1 \in \SS_1, B_2 \in \SS_2\}).
\end{align*}
\end{exe}
\begin{lemma}
Let $X_i : (\Omega, \FF) \to (S_i, \SS_i)$, $i=1,2, \ldots,d$,
be random elements.
Let $S= S_1 \times \cdots \times S_d$, 
$\SS = \SS_1 \otimes \cdots \otimes \SS_d$.
Then $(X_1, \ldots, X_d) : (\Omega, \FF) \to (S, \SS)$  is a random element.
%The $\sigma$-algebra generated by $(X_1, \ldots, X_d)$
%is, as above,
%\[
%\sigma(X_1, \ldots, X_d) = \{(X_1, \ldots, X_d)^{-1}(B), B \in \BB(\R^d)\}.
%\]
%Furthermore,
%\[
%\sigma(X_1, \ldots, X_d) = \sigma(X_1) \vee \cdots \vee \sigma(X_d).
%\]
\end{lemma}

%Moreover, and more importantly for all the theory
%of stochastic processes, we can carry this to infinity. 
%Let $(S_i, \SS_i)$, $i=1,2,\ldots$, be measurable spaces.
%We wish to consider the space $S = \times_{i=1}^\infty S_i$
%and endow it with a natural $\sigma$-algebra $\SS$. To do so,
%consider sets of the form $B_1 \times B_2 \times \cdots$\footnote{
%Each such set is called `finite-dimensional rectangle'.
%}
%where $B_i \in \SS_i$ for all $i$, and where $B_j = S_j$ for
%all but finitely many indices $j$.
%Define $\SS = \bigotimes_{i=1}^\infty  \SS_i$
%to be the smallest $\sigma$ algebra containing all these sets.
%\begin{lemma}
%Suppose that for each $i \in \N$,  $X_i: (\Omega, \FF) \to (S_i, \SS_i)$
%is a random element. 
%Let $S = \bigtimes_{i=1}^\infty S_i$ and let $X=(X_1, X_2, \ldots):
%(\Omega, \FF) \to (S, \SS)$, where $\SS = \bigotimes_{i=1}^\infty  \SS_i$
%is the product-sigma algebra.
%Then $X$ is a random element.
%\end{lemma}


\begin{exe}
\label{drill4}
Show that, if $X=\1_A$, the indicator of a set $A$, then
$\sigma(\1_A) = \{\varnothing, A, A^c, \Omega\}$.
Consider next two subsets $A_1, A_2$ of $\Omega$ and prove that the 
$\sigma$-algebra generated by $c_1\1_{A_1} + c_2 \1_{A_2}$ is
\begin{multline*}
\sigma(c_1\1_{A_1} + c_2 \1_{A_2}) = 
\{\varnothing,~ \Omega,~
A_1,~ A_2,~ 
A_1^c,~ A_2^c,~ 
A_1A_2,~ A_1 A_2^c,~ A_1^c A_2,~ A_1^c A_2^c,~
\\
A_1 \cup A_2,~ A_1 \cup  A_2^c,~ A_1^c \cup  A_2,~ A_1^c \cup  A_2^c,~
A_1 \xor A_2,~
(A_1 \xor A_2)^c
\}.
\end{multline*}
\end{exe}
\begin{exe}
Consider the following partition of $\Omega$:
%It is more convenient to represent this $\sigma$-algebra by the 
%partition of $\Omega$ generated by $A_1, A_2$, i.e.\ by the
%collection of disjoint sets
\[
\{
A_1 A_2, ~ A_1 \setminus A_2, ~ A_2 \setminus A_1, ~ (A_1 A_2)^c
\}.
\]
Show that any nonempty set in Exercise \ref{drill4} can be obtained as union of
elements of this partition.
\end{exe}
\begin{exe}
\label{drill6}
Given a partition $\CC =\{C_1, \ldots, C_n\}$ of $\Omega$ show that
the $\sigma$-algebra generated by $\CC$ consists of the empty set and
all sets that can be obtained by taking unions of sets in $\CC$.
Assuming that none of the $C_i$ is empty, this $\CC$ contains 
exactly $2^n$ sets.
Also show that any random variable that takes value $b_i$ on $C_i$ for each $i$
generates a $\sigma$-algebra which is contained in $\sigma(\CC)$. Show
that if the values $b_i$ are distinct then $\sigma(X) = \sigma(\CC)$.
\end{exe}

If $X, Y$ are random variables on a common measurable space $(\Omega, \FF)$
(and values in arbitrary sets)
we say that {\sc $Y$ is measurable with respect to $X$, often
written as $X \in \sigma(Y)$} if 
\[
\sigma(Y) \subset \sigma(X).
\]
\begin{lemma}
\label{fof}
If $X: (\Omega, \FF) \to (S, \SS)$, $Y: (\Omega, \FF) \to (\R, \BB)$
are random variables, and if $Y \in \sigma(X)$, then
there exists a random variable (measurable map) 
$H: (S, \SS) \to (\R, \BB)$ such that $Y = H \comp X$.
\end{lemma}
%\begin{exe}
%Show that if $X(\Omega)=\{x_1, \ldots, x_n\}$ is a finite set
%then $\sigma(X)$ is generated by the partition 
%$\big\{\{X=x_i\}, ~ i=1,\ldots,n\big\}$ of $\Omega$.
%\end{exe}
\begin{exe}
Using Exercise \ref{drill6} show that any $Y$, measurable with respect to
$X$, must be of the form
\[
Y = \sum_{i=1}^n c_i \1(X=x_i).
\]
\end{exe}
We then see that what is claimed in Lemma \ref{fof} is correct, in this
special situation with $X$ being finitely-valued. Indeed, let
$H(x) = \sum_{i=1}^n c_i \1(x=x_i)$ and, obviously, $Y = H \comp X$.


The general case requires an approximation result that says that
any measurable random variable $X: (\Omega, \FF) \to (\R, \BB)$ can
be approximated by simple random variables. A {\sc simple random
variable} is a random variable with finitely many values.
\begin{lemma}
\label{sa}
Let $X : (\Omega, \FF) \to (\R, \BB)$. Then there exists
a sequence $X_1, X_2, \ldots$ of simple random variables such that
$\lim_{n\to\infty} X_n(\omega) = X(\omega)$.
If $X(\omega) \ge 0$, $\omega \in \Omega$, we can choose the sequence so that
$0 \le X_n(\omega) \le X_{n+1}(\omega)$ for each $n$ and $\omega$.
\end{lemma}
The proof of Lemma \ref{sa} can be found in \cite{k} and is based on
defining
\begin{gather*}
\tau_n(x) := 2^{-n} \lceil 2^n x\rceil  \wedge n, \quad
X_n(\omega):= \tau_n(X(\omega)), 
\end{gather*}
and the observation that $X_n$ converges to $X$.

\begin{exe}
Let $X$ be one random variable in $\R$. Show that $\sigma(X^2)$
is a strict subset of $\sigma(X)$. But show that $\sigma(2^X) = \sigma(X)$.
\end{exe}




\subsection{Law (or distribution) of a random element (or variable)}
The reader will of course have noticed that 
the concept of ``random element'' has nothing to 
do with randomness.\footnote{
The name is justified because of the way the concept is used.}
Let $\Pr$ be a probability on $(\Omega, \FF)$.
The {\sc distribution} or {\sc law}
of the random element $X$ is a probability $\Pr_X$ on
$(S, \SS)$ which is generated, in the most natural fashion, by $X$:
\[
\Pr_X(B) = \Pr(X^{-1}(B)), \quad B \in \SS.
\]
Note that $\Pr_X$ depends on two functions: the function $\Pr$ and 
the function $X$. 
\begin{exe}
Show that if $(\Omega, \FF, \Pr)$ is a probability space
and $X: (\Omega, \FF) \to (S, \SS)$ a random element then
$(S, \SS, \Pr_X)$ is a probability space.
Hence if $X$ is a random vector then $X_1$ is a random variable.
\end{exe}
\begin{exe}
With the notation of Exercise \ref{drill1}, show that the law of $H \comp X$
as a random element on the probability space $(\Omega, \FF, \Pr)$ is
the same as the law of $H$ as a random element on $(S, \SS, \Pr_X)$.
\end{exe}
So the role of a random element is to transform an abstract probability space
into a concrete one.
In practise, one is often given\footnote{
Actually, one is seldom given anything. Either one derives something from
some basic principles/requirements or one performs an experiment 
whereby measurements are collected and a probability measure is 
stipulated. The latter is the subject of Statistics.}
a probability measure $\Qr$ on some 
$(S, \SS)$ and one may (or may not)
want to construct a probability space $(\Omega, \FF, \Pr)$ and
a random variable $X:(\Omega, \FF) \to (S, \SS)$ such that $\Pr_X=\Qr$. 
In the absence of any further requirement we %follow Occam's razor
consider the so-called {\sc canonical construction}: take
$\Omega=S$, $\FF=\SS$, $\Pr=\Qr$ and let $X(\omega) \equiv \omega$.
Then, obviously, $\Pr_X = \Qr$.
%If this appears to be silly then this is because it is. But silly things
%are often quite useful. On the other hand, if other requirements are
%needed to be satisfied, choosing the ``right'' probability space
%and the ``right'' random variable is an art.
%The freedom in the choice of probability space can be roughly compared
%to the freedom of choice of an appropriate coordinate system in $\R^3$
%when dealing, e.g.\ with the solution of a certain physical problem expressed
%in terms of a partial differential equation. For example, when we study
%the motion of fluid in a cylinder we may want to choose cylindrical
%coordinates.





\subsection{Law of a discrete random variable}
\label{law}
A {\sc discrete random variable} $X : (\Omega, \FF) \to (S, \SS)$
is, by definition, one that takes countably many values.
In other words, if $\Pr$ is a probability on $(\Omega, \FF)$ then
$X$ is discrete if and only if there is a countable set $D \in \SS$
such that $\Pr(X \in D)=1$.
We also assume that $D$ and all its subsets are members of $\SS$.
Hence the law $\Pr_X$ of $X$ is a probability on $D$.
We know that a probability on a countable set $D$ can be defined by
defining its values on singletons. These values form the so-called
{\sc probability mass function}. 
%(a terminology which will become obsolete once adulthood is reached).
Thus, the probability mass function is
\[
p (x) 
= \Pr_X\{x\}
= \Pr(X =x) ,
\quad x \in D.
\]
Clearly, if $B \subset D$ then 
\[
\Pr_X(B) = \Pr_X\bigg(\bigcup_{x \in B} \{x\}\bigg) =
\sum_{x \in B} p(x).
\]
So $p$ is sufficient for computing $\Pr_X$.
%\begin{example}
%A box contains $n$ socks labelled 1 through $n$. 
%Pick two socks at random and let $X$ be the pair of their labels.
%Then $X$ is a discrete random variable taking values $(i,j)$ where
%$1 \le i, j \le n$, $i \neq j$. The probability mass function is
%\[
%p(i,j) = 1/n(n-1).
%\]
%But what is the probability space? First, we should realise that we do not
%necessarily need to consider it. Second, we should realise that the article
%``the'' is wrong, for there are many choices for a probability space.
%Having said that, a reasonable choice for $\Omega$ is the
%set of permutations $\omega$ of $\{1, \ldots, n\}$, i.e.\
%$\omega=(\omega_1, \ldots, \omega_n)$ where all the $\omega_i$ take
%values in $\{1, \ldots, n\}$ and are distinct. The $\sigma$-algebra $\FF$ 
%should be rich enough to contain all singletons, i.e.\ $\FF=2^\Omega$. The
%probability  $\Pr$ should be defined as $\Pr(\{\omega\}) = 1/n!$ for all
%$\omega$.
%To be honest we should check that $p(i,j) = \Pr\{\omega\in \Omega: \omega_1=i,
%\omega_2=j\}$.
%We have 
%\[
%\Pr\{\omega\in \Omega: \omega_1=i, \omega_2=j\}
%= \frac{1}{n!} ~\sharp \{\omega\in \Omega: \omega_1=i, \omega_2=j\}
%= \frac{(n-1)!}{n!} = \frac{1}{n(n-1)},
%\]
%as required. So $(\Omega, \FF, \Pr)$ is a probability space,
%$X$ is a random variable (check this!), $\Pr_X$ is its law,
%and $p$ is its probability mass function.
%\end{example}
%
%\begin{example}
%Consider the experiment of picking $k$ integers at random
%(with replacement) from the set $\{1, \ldots, n\}$. Our
%$(\Omega, \FF)$ here can be taken to be
%\[
%\Omega = \{1, \ldots, n\}^k, \quad \FF = 2^\Omega,
%\]
%and the probability corresponding to the experiment should be
%defined as 
%\[
%\Pr\{(\omega_1, \ldots, \omega_k)\} = \frac{1}{n^k}.
%\]
%Note here that $\{(\omega_1, \ldots, \omega_k)\}$ is a set containing
%a single point, namely the ordered $k$-tuple 
%$\omega=(\omega_1, \ldots, \omega_k)$.
%For more general sets $B$ we take, as required, $\Pr(B) = \sum_{\omega \in B}
%\Pr\{\omega\} = \frac{\sharp B}{n^k}$.
%Define a random variable representing the maximum number picked:
%\[
%X(\omega) = \max(\omega_1, \ldots, \omega_k).
%\]
%Clearly, $X$ takes values in $\{1, \ldots, n\}$ and trivially,
%$X$ is a measurable function from $(\Omega, \FF)$ to $(\{1, \ldots, n\}, 
%2^{\{1, \ldots, n\}})$. (The inverse image of a subset of $\{1, \ldots, n\}$
%under $X$ is, of course, a subset of $\Omega$, i.e.\ an element of $\FF$.)
%Let us compute the probability mass function for $X$.
%For $x \in \{1,\ldots,n\}$ we have
%\begin{align*}
%p(x) &= \Pr(X^{-1}(x)) = \Pr(X = x) 
%= \Pr\{\omega \in \Omega:~ \max(\omega_1, \ldots, \omega_k)=x\}
%\\
%&=  \Pr\{\omega \in \Omega:~ \max(\omega_1, \ldots, \omega_k) \le x
%\text{ but } \max(\omega_1, \ldots, \omega_k) \not \le x-1\}
%\\
%&= \Pr\{\omega \in \Omega:~ \max(\omega_1, \ldots, \omega_k) \le x\}
%- \Pr\{\omega \in \Omega:~ \max(\omega_1, \ldots, \omega_k) \le x-1\}
%\\
%&= \frac{1}{n^k} \sharp\{\omega \in \Omega:~ \omega_1\le x , \ldots, \omega_k \le x\}
%-\frac{1}{n^k}  \sharp\{\omega \in \Omega:~ \omega_1 \le x-1, \ldots, \omega_k \le x-1\}
%\\
%&= \frac{x^k-(x-1)^k}{n^k}.
%\end{align*}
%\end{example}

%If we were to deal ONLY with discrete random variables then there would be
%no need to introduce many of the concepts introduced above. However, one
%soon realises that one has to move...
\begin{exe}
Suppose that the random variable $X$ takes $n$ distinct values (i.e.\
$X(\Omega)$ is a set with $n$ elements). Show that $\sigma(X)$ has
$2^{2^n}$ elements and describe (give a procedure for describing) them.
\end{exe}


\subsection{Uniform random variable and continuous random variables}
A uniform random variable $U$ in the interval $[0, 1]$ is such that its
law satisfies $\Pr_U([a,b])=b-a$ for all $0 \le a \le b \le 1$.
To show that such a random variable exists is hard and the reader is
referred to \cite{k}, for an approach based on using the probability
space $\Omega = \{0, 1\}^\N$. A more standard approach is
to define $U(x)=x$, $x \in [0,1]$, where $[0,1]$ is endowed with
the Borel $\sigma$-algebra and the Lebesgue measure $\Pr$.
Having shown that the latter exists, we simply observe that $\Pr_U$ is
the law of a uniform random variable.
Notice that if $D$ is a countable set then
\[
\Pr(U \in D) = 0.
\]
For example, $\Pr(U \text{ is rational number }) =0$.

If $F: \R \to \R$ is a nondecreasing continuous function with
$\lim_{x \to -\infty} F(x)=0$, $\lim_{x \to \infty} F(x)=1$,
and if $F^{-1}(u) := \inf\{x \in \R: F(x) >u\}$
then $X=F^{-1}(U)$ is a random variable that shares something in
common with $U$, namely,
\[ 
\Pr(X \in D)=0,
\]
if $D$ is a countable set. Such a random variable is called continuous.



\section{Distribution functions}
The distribution function of a random variable $X$ is defined by:
\begin{equation}
\label{DF}
F(x) := \Pr_X(-\infty, x], \quad x \in \R.
\end{equation}
This function is useful because:
\begin{lemma}
\label{314}
Knowledge of $\Pr_X$ on this class of sets only (semi-infinite
intervals) implies knowledge of $\Pr_X$ on the whole of $\BB$. 
\end{lemma}
For a proof, see \cite{k}.
Next, here are some properties of $F$:
\begin{lemma}
\label{kkk}
(i) $x_1 < x_2 \Rightarrow F(x_1) \le F(x_2)$,
(ii) $\lim_{x\to-\infty} F(x) =0$,
(iii) $\lim_{x\to+\infty} F(x) =1$,
(iv) $\lim_{n \to \infty} F(x+1/n) = F(x)$. 
\end{lemma}
%\begin{proof}
%(i) If $x_1 < x_2$ we have $(-\infty, x_1] \subset (-\infty, x_2]$
%and so $\Pr_X (-\infty, x_1] \le \Pr_X (-\infty, x_2]$.
%(ii)\&(iii) Since $F$ is monotonic with values between $0$ and $1$
%it has a limit both as $x$ tends to $-\infty$ and $+\infty$.
%We have $\cap_{n \in\Z} (-\infty, n] = \varnothing$, so $\Pr_X(-\infty, n]
%\to 0$ as $n \to -\infty$. Similarly, $\cup_{n \in \Z} (-\infty,n] = \R$,
%so $\Pr_X(-\infty, n] \to \Pr_X(\R)=1$ as $n \to +\infty$.
%(iv) $\cap_n(-\infty, x+1/n]= (-\infty, x]$.
%\end{proof}

\noindent{\bf Remark:}\\
%1. Notice that $F(x-1/n)$ does NOT necessarily converge to $F(x)$
%because $\cup_n(-\infty, x-1/n] = (-\infty, x)$, and so $\lim_{n\to\infty}
%F(x-1/n) = \Pr_X(-\infty, x)$ which will be different from $\Pr_X(-\infty, x]$
%if $\Pr_X\{x\} > 0$.
%\\
%2. 
There is no good reason that we chose this class of sets, other than
people have been using it by convention. For instance, we could have
chosen open semi-infinite interval $(-\infty, x)$, in which case (iv) of
Lemma \ref{kkk} would be replaced by $\lim_{n \to \infty} F(x-1/n) = F(x)$.

\begin{definition}
A function $F : \R \to \R$ is called distribution function iff
(i) $x_1 < x_2 \Rightarrow F(x_1) \le F(x_2)$,
(ii) $\lim_{x\to-\infty} F(x) =0$,
(iii) $\lim_{x\to+\infty} F(x) =1$,
(iv) $\lim_{n \to \infty} F(x+1/n) = F(x)$.
\end{definition}

\begin{corollary}
If $F$ is a distribution function then there exists a probability $\Qr$
on $(\R, \BB)$ such that $\Qr(-\infty, x] = F(x)$ for all $x \in \R$.
\end{corollary}

\begin{lemma}
\label{intervals}
Let $X$ be one real random variable with law $P_X$ and distribution function
$F(x) = \Pr_X(-\infty, x]$, $x \in \R$.
Then (i) $\Pr(X \in (a, b]) = F(b)-F(a)$, (ii) $\Pr(X \in (a,b)) = F(b-)-F(a)$,
(iii) $\Pr(X \in [a, b]) = F(b) - F(a-)$,
(iv) $\Pr(X=a) = F(a)-F(a-)$.
\end{lemma}

\begin{exe}
Carefully justify the formulae in the proof of Lemma \ref{intervals}.
\end{exe}



\subsection{Types of distribution functions}
We now discuss the various kinds of distribution functions
on $\R$.
\subsubsection{Discrete distribution functions}
A discrete distribution function is the distribution function of
a discrete random variable $X$ with values in some countable subset $S$ of $\R$.
Assume that $p(s) = \Pr(X = s) > 0$ for all $s \in S$.
Such a distribution function
satisfies $F(s)-F(s-) > 0$ for all $s \in S$.
Indeed, $F(s) - F(s-) = \Pr(X=s)$.
Also, if $(a,b)$ is an open interval containing no points 
of $S$, then $F$ is constant on $(a,b)$. Indeed,
if $a < x < b$ then $F(x)-F(a) = \Pr(a < X \le x) = \sum_{s \in S, a < s \le x}
\Pr(X=s) =0$. 
\begin{example}
Let $X$ be a random variable such that $\Pr(X=n) = 2^{-n}$, $n \in \N$.
Then its distribution function looks like in Figure \ref{ddf}.
\begin{figure}[ht]
\centerline{\includegraphics[width=6cm]{figs/ddf.eps}}
\caption{Distribution function of a discrete random variable}
\label{ddf}
\end{figure}
\end{example}

\begin{example}
Let $X$ be a random variable such that for every rational number
of the form $m/n$ where $m, n$ are integers with no common factors,
we have $\Pr(X=m/n) = c 2^{-(m+n)}$ where $c$ is chosen
so that $\Pr(X \in \Q) =1$.
Its distribution function is discrete because $\Q$ is countable.
Unfortunately, I can't draw it. (There are no intervals $(a, b)$ containing
no rational points.)
\end{example}

\subsubsection{Continuous distribution functions}
A distribution function $F$ is continuous if it is a continuous function,
i.e.\ if $F(x) - F(x-) =0$ for all $x \in \R$.
\begin{example}
Consider the random variable $U$ with $\Pr(U \le u) = u$ for all $u \in [0,1]$.
Such a random variable exists (we constructed it). Its distribution function
looks like in Figure \ref{cdf}.
\begin{figure}[ht]
\centerline{\includegraphics[width=3cm]{figs/cdf.eps}}
\caption{An absolutely continuous distribution function}
\label{cdf}
\end{figure}
\end{example}
Excepting the points $0, 1$ we have that it is also differentiable
with derivative $f(u) = 1$ if $0 < u < 1$ and $0$ otherwise..
If we arbitrarily define $f(0) = f(1) =0$, we also have 
$\int_{-\infty}^u f(t) dt = F(u)$ for all $u \in \R$.
We like such distribution functions:
\subsubsection{Absolutely continuous distribution functions}
A distribution function $F$ is called {\sc absolutely continuous}
if there exists a function $f$ (called {\sc density} of $F$) such that
\[
F(x) = \int_{-\infty}^x f(t) dt, \quad x \in \R.
\]
\footnote{
The integral in the display is a Lebesgue integral. 
For a definition, see \cite{wil}.
For the time being, you may think of it as the standard Riemann integral
of Integral Calculus.
}
The density is not uniquely defined. For instance, it can be changed
on a finite set and such a change will not affect the integral above.
Usually, one\footnote{
unconsciously}
imposes additional regularity conditions, such as continuity,
resulting in uniqueness.

But not all continuous distribution functions are absolutely continuous:
\subsubsection{Singularly continuous distribution functions}
A distribution function $F$ is called {\sc singularly continuous}
if it is continuous but not absolutely continuous.
We need to show that there are such functions.
\begin{exe}
\label{ccce}
Consider the space $(\Omega=\{0,1\}^\N, \FF, \Pr)$, where
$\FF$ is the product $\sigma$-algebra, and $\Pr$ is such that
$\Pr\{\omega \in \Omega: \omega_1=i_1, \ldots, \omega_n=i_n) = 2^{-n}$,
$i_1, \ldots, i_n \in \{0,1\}$, $n \in \N$. Let
\[
V(\omega) := \sum_{n=1}^\infty \frac{2\omega_n}{3^n}.
\]
%In Exercise \ref{ccce} you are asked to show that $V$ has a continuous
%distribution function which is not absolutely continuous. Therefore
%$V$ has no density.
\begin{figure}[ht]
\centerline{\includegraphics[width=4cm]{figs/sdf.eps}}
\caption{A continuous distribution function without density}
\end{figure}
Show that the random variable $V$ defined in Example \ref{ccce} has a continuous
but not absolutely continuous distribution function.
\end{exe}

\subsubsection{General distribution functions}
Suppose that $F, G$ are distribution functions. Then, for any
$\lambda \in (0,1)$, the function $\lambda F + (1-\lambda G)$ is
a distribution function. (Probabilistically,  if $X, Y$ are random variables
with distribution functions $F, G$, respectively, then we can define
a new random variable $Z$ which equals $X$ with probability $\lambda$
or $Y$ with probability $1-\lambda$.)
So, if $F$ is discrete and $G$ continuous then $\lambda F + (1-\lambda G)$
is neither discrete nor continuous: it is mixed.
The question is: Can we exhaust all distribution functions by taking
mixtures of the three types mentioned above?
The answer is yes:
\begin{theorem}
Let $F$ be a distribution function on $\R$. Then $F$ can be {\em uniquely}
written as 
\[
F= \lambda_d F_d + \lambda_{ac} F_{ac} + \lambda_{sc} F_{sc}
\]
where $F_d, F_{ac}, F_{sc}$ are discrete, absolutely continuous, singularly
continuous distribution functions, respectively, and where the coefficients
are nonnegative such that $\lambda_d + \lambda_{ac} + \lambda_{sc}=1$.
\end{theorem}
The last two terms of this decomposition are known as the
continuous part of $F$. The first two terms are known as the
singular part of $F$. We will not prove this theorem, but refer, e.g.\
to \cite{hs}.

\subsubsection{Differentiation: a word of caution}
The subject of densities involves the concept of a derivative of
functions that are not necessarily everywhere differentiable. 
Mimicking the definition of a density, we will say that a function $G$
has density $g$ if $G'(x) = g(x)$ for almost all $x$. The latter statement
means that it holds true that $G'(x) = g(x)$ for all $x$ in some set $A$
whose complement is small in the sense that for all $\epsilon > 0$
there exist intervals $I_n$, $n \in \N$ with lengths $\lambda_n$, $n \in \N$,
such that $\sum_n \lambda_n < \epsilon$ and $A^c \subset \cup_n I_n$.
For further elaboration on this important notion, without which
the concept of a density cannot be properly understood, see \cite{hs,k}.
\begin{exe}
Show that a continuous and piecewise differentiable function $G$
is almost everywhere differentiable.
\end{exe}



\section{Transformation rules and densities}
Consider a random variable $X : (\Omega, \FF) \to (\R, \BB)$.
Suppose $\Pr$ is a probability on $(\Omega, \FF)$. We are interested
in the distribution $\Pr_X$ of $X$. Suppose, for some reason, we don't like
it and want to change it to something else. There are two ways to do this.
First, we can change the probability $\Pr$ and replace it by some other
probability $\Qr$. Then $\Pr_X$ will be replaced by $\Qr_X$.
Second, we can take a function $H: (\R, \BB) \to (\R, \BB)$
and replace $X$ by $H\comp X$. Then $\Pr_X$ is replaced by 
$\Pr_{H \comp X}$. The two procedures are not, in general, equivalent.

Suppose, for instance, that $X$ is a discrete random variable. Then 
any one-to-one function $H$ will not change the probabilities of
singletons $\{s\}$ such that $\Pr_X\{s\}>0$, but, merely, will
rename them: $\{s\}$ will be transformed to $\{H(s)\}$ and its
probability will remain the same.
Even if $H$ is not one-to-one, there is not much that $H$ can do to
change the probabilities. Consider, for instance, a random variable $X$
with values $1, 2, 3$ and probabilities $p_1, p_2, p_3$, respectively.
Then the most a function $H$ can do is either be one-to-one, in
which case $H(1), H(2), H(3)$ will retain the old probabilities,
or map two points, say $1, 2$, to a single point,
with probability $p_1+p_2$ and leave the the third intact.
Thus, the types of changes in the distribution of 
a discrete $X$ that can be achieved by taking a function 
of it are quite restricted. To really change its distribution {\em ad libitum},
we need to change the underlying probability $\Pr$.

For the case of absolutely continuous random variables, the story is
different: a merely one-to-one function $H$ can simultaneously
change the values and the distribution in a quite general fashion.

\begin{theorem}
\label{denstrans}
Let $X$ be an absolutely continuous random variable in $\R$ with density $f$.
Let $\phi : \R \to \R$ be strictly increasing differentiable function
and let $\psi$ be its inverse function.
Then $\phi(X)$ a random variable with absolutely continuous
distribution function and density
\[
\psi'  \cdot f \comp \psi \text{ on } \phi(\R),
\]
and $0$ elsewhere.
\end{theorem}
\begin{proof}
Since $\phi$ is strictly increasing, its inverse function exists
and has domain $\phi(\R)$. Then, the distribution function
of $\phi(X)$ is, for any $t \in  \phi(\R)$,
\[
\Pr(\phi(X) \le t) = \Pr (X \le \psi(t)) = \int_{-\infty}^{\psi(t)}
f(x) dx.
\]
By changing variable in the integral we have
\[
 \int_{-\infty}^{\psi(t)} f(x) dx
= \int_{-\infty}^t f(\psi(s)) {\psi}'(s) ds,
\]
where we set $\psi'(s) =0$ for $s \not \in \phi(\R)$.
{From} the definition of an absolutely continuous distribution function we see
that, indeed, $\phi(X)$ has absolutely continuous distribution function
and its density is the function inside the last integral.
\end{proof}

\begin{exe}
Let $U$ be a uniform random variable in the interval $(0,1)$. Find the
density function of $e^{e^U}$.
\end{exe}

Theorem \ref{denstrans} assumes that $\phi$ is strictly increasing.
It is immediate to find out the formula for strictly decreasing $\phi$.
Generalising to more general functions is possible and relatively easy
for random variables with values in $\R$ (the story in $\R^d$ is
more complicated). For instance, we may assume that $\phi$ is
piecewise differentiable. The problem becomes a problem in differential
calculus and the general theorem is omitted. However, an example
is due:
\begin{exe}
Let $X$ be a random variable with density $f(x) = c(1+x^2)^{-1}$,
$x \in \R$. Let $\phi(x) = \cosh(x)$. Find the density (and hence
show that it exists) of $\phi(X)$.
\end{exe}


\section{Expectation} 
The expectation $\E X$ of one real random variable $X$ is, if it can be defined,
justified (for instance) by the Theorem (Law) of Large Numbers which will be
proved at a later chapter.
It is easy to define the expectation of a discrete random variable $X$
with values in $\R$ and probability mass function $p(x)$. Let
$S$ be the set of $x$ such that $p(x) > 0$. Then
\[
\E X   = \sum_{x \in S} x p(x),
\]
provided that this sum can be defined.
We know from Analysis (see \cite{hs}) that the sum of positive numbers
can be defined irrespective of which order we sum the numbers up. However,
not all the summands above are necessarily positive. So let us
consider the positive and negative terms separately and try to define
\[
\E X = \sum_{x \in S_+} x p(x) - \sum_{x \in S_-} (-x) p(x),
\]
where $S_+ := \{ x \in S:~ p(x) > 0\}$, 
where $S_- := \{ x \in S:~ p(x) < 0\}$.
Each of the two sums, separately, is a sum of positive terms, hence it
is well-defined. The only ``problem'' is that such a sum can take 
value $+\infty$. If both sums are finite then $\E X$ is a finite number.
If the first sum is $+\infty$ but the second finite then $\E X =
+\infty$. Similarly, if the first is finite but the second infinite,
then $\E X = -\infty$. The only case where we cannot talk (cannot define)
$\E X$ is when both sums are infinite.

When $X$ has absolutely continuous distribution function with density $f$,
one can define $\E X$ similarly:
\[
\E X = \int_0^{\infty} x f(x) dx - \int_{-\infty}^0 (-x) f(x) dx,
\]
provided that not both integrals are infinity.

The general case requires an approximation procedure, known as integral
with respect to a measure. 
When $X$ is a nonnegative 
random variable, there always exists a sequence $\xi_n$
of nonnegative random variables, each of which takes finitely many values,
such that $\xi_n(\omega) \to X(\omega)$, as $n \to \infty$,
for all $\omega \in \Omega$.
We then define
\[
\E X = \lim_{n \to \infty} \E \xi_n.
\]
It can be proved \cite{k} that the limit exists
and is independent of the approximation procedure.
If $X$ has no restriction on sign, we define
\[
\E X = \E X^+ - \E X^-,
\]
provided that not both terms are $+\infty$.



We say that $X$ is integrable (with respect to $\Pr$) if
both $\E X^+$ and $\E X^-$ are finite or, equivalently,
if $\E |X| < \infty$. (The latter follows from the identity
$|x| = x^+ + x^-$.)


\begin{lemma}[algebraic properties of expectation]
\label{alg}
Suppose  $X, Y$ are integrable random variables on the same
probability space $(\Omega, \FF, \Pr)$. Then:\\
(i) If $\Pr(A)=0$ then $\E X \1_A = 0$.
\\
(ii) $\E (c X) = c \E(X)$ for all $c \in \R$.
\\
(iii) $\E(X+Y) = \E X + \E Y$.
\\
(iv) If $\Pr(X \ge 0)=1$ then $\E X \ge 0$.
If $\Pr(X \le Y)=1$ then $\E X \le \E Y$.
\end{lemma}

\begin{theorem}[monotone convergence theorem]
\label{mct}
For ANY sequence $X_n$ of nonnegative random variables such that
$X_n \uparrow X$, we have $\E X_n \uparrow \E X$.
\end{theorem}

\begin{lemma}[Fatou's lemma]
\label{fatou}
For any sequence $X_n$ of nonnegative random variables, $\E \liminf X_n
\le \liminf \E X_n$.
\end{lemma}


If $A \in \FF$ we can define the expectation of $X$ on $A$ by:
\[
\E (X; A) := \E(X \1_A).
\]
If $\Pr(A) > 0$ we can define the expectation of $X$ given $A$ by:
\[
\E(X | A) := \frac{\E(X; A)}{\Pr(A)}.
\]
We remark that $\E(X|A)$ is expectation with respect to the restriction
$\Pr_A$ of $\Pr$ on $A$, i.e.\ with respect to the probability 
\[
\Pr_A : \FF \to \R; \qquad \Pr_A(B) := \Pr(AB), \quad B \in \FF.
\]
In other words,
\[
\E(X | A) = \E_{\Pr_A} X.
\]

\begin{exe}
Show that $|\E X| \le \E |X|$ (whenever $\E X$ is defined).
\end{exe}

\begin{theorem}[Dominated Convergence Theorem]
\label{dct}
Let $X_n$ be a sequence of random variables such that 
$X(\omega) = \lim_{n \to \infty} X_n(\omega)$ exists and
such that $|X_n(\omega)| \le Y(\omega)$ for all $n$ and $\omega$,
and $\E |Y| < \infty$.
Then $\E|X_n-X|$ converges to zero.
\end{theorem}
%\begin{proof}
%Apply Fatou's lemma \ref{fatou} to $2Y-|X_n-X|$.
%\end{proof}



\subsection{Substitution rule} % and chain rules}
There is a little problem with the notation $\E X$ in that it uses
the same letter regardless of the probability $\Pr$. More correctly,
one should write
$\E_P X$ instead of $\E X$ or $\int_\Omega X d\Pr$.
Let us consider compositions of random elements.
\begin{lemma}
\label{subst}
Consider the measurable functions
\[
(\Omega, \FF) \xrightarrow[]{Z} (S, \SS) \xrightarrow[]{H} (\R, \BB).
\]
Let $\Pr$ be a probability on $(\Omega, \FF)$. Let $\Pr_Z$ be the law
of $Z$.
Then
\[
\E_{\Pr} H \comp Z = \E_{\Pr_Z} H,
\]
whenever either side exists.
(Here, $H \comp Z$ is one real random variable on the
probability space $(\Omega, \FF, \Pr)$ and
$H$ is one real random variable on the probability space $(S, \SS, \Pr_Z)$.)
\end{lemma}
{\bf Sketch of proof:}
Suppose $H$ is an indicator random variable, i.e.\ $H = \1_B$ for
some $B \in \SS$. Then $\E_{\Pr_Z} \1_A = \Pr_Z(A)$ by the definition
of the expectation of a simple random variable. On the other hand,
$H \comp Z = \1_A(Z)$ is an indicator random variable on $(\Omega, \FF)$: it
is the indicator of the set $\{\omega \in \Omega:~ Z(\omega) \in A\}$.
Hence, again by the by the definition
of the expectation of a simple random variable,
$\E_{\Pr} H \comp Z = \Pr(Z \in A)$.
But $\Pr_Z(A) = \Pr(Z \in A)$ by the definition of the law
of the random variable $Z$ (see section \ref{law}).
Suppose next that $H$ is a simple random variable. Use the above and
linearity of expectation to get the result.
Suppose that $H$ is a general random variable.
Use an approximation by simple random variables to conclude.
\qed

\begin{corollary}[the expectation of a random variable depends only on its law]
\label{iii}
If $X$ is a real random variable on $(\Omega, \FF, \Pr)$ with expectation
$\E_{\Pr} X$ and law $\Pr_X$ then
\[
\E_{\Pr} X = \E_{\Pr_X}\iota
\]
where $\iota: \R \to \R$ is the identity function: $\iota(x) \equiv x$.
\end{corollary}

Suppose that $X$ is a discrete random variable with values in
a finite set $S \subset \R$ and probability mass
function $p(x), x \in S$.
Since $X = \sum_{x \in S} x \1(X=x)$ is a simple random variable, 
we immediately have that $\E X = \sum_{x \in S} x \Pr(X=x) = \sum_{x \in S}
x p(x)$, as needed.
The same formula holds for a discrete random variable with values
in a countable set $S$: Simply enumerate the elements of $S$
and use monotone convergence theorem.

Let us now consider an absolutely continuous random variable $X$
with density $f$. We would like to show that $\E X$ is compatible with
the definition given at the beginning of the section, namely that it
equals $\int_\R x f(x) dx$. To do this, requires understanding of
Lebesgue-Stieltjes integral. The step is omitted and can be found in
\cite{fg,wil}, and in \cite{k}.


\begin{lemma}
\label{chainrule}
Let $\Pr_X$ be the law of a random variable $X$ with density $f$.
Then, for any measurable $g : (\R, \BB) \to (\R, \BB)$,
\[
\int_\R g(x) f(x) dx = \E_{\Pr_X} g
\]
provided that wither side exists.
\end{lemma}
If you want to see the proof, look at \cite{k}. But do notice that,
if $g = \1_B$, then this is what was discussed before the Lemma.
For $g$ simple, we use linearity. For general $g$ we approximate.

\begin{corollary}
Let $\Pr_X$ be the law of an integrable random variable $X$ with density $f$.
\\
(i) If $\iota$ is the identity function on $\R$ then
\[
\int_\R x f(x) dx = E_{\Pr_X} \iota.
\]
(ii) 
\[
\E X = \int_\R x f(x) dx.
\]
\end{corollary}
The proof of
(i) follows from Lemma \ref{chainrule} with $g = \iota$.
The proof of
(ii) follows from corollary \ref{iii}.




\begin{exe}
Suppose that $Z$ is a real random variable with absolutely continuous
distribution function and density $f_Z$. Let $H: (\R, \BB) \to (\R, \BB)$
be a measurable function. Suppose that the random variable $X=H(Z)$ has
density $f_X$. Show that the expectation of $X$ (if it exists)
can be computed in two ways:
\[
\E X = \int_\R x f_X(x) dx = \int_\R H(z) f_Z(z) dz.
\]
\end{exe}

\begin{exe}
Let $B \in \BB$ and let $\lambda(B) := \int_\R \1_B(x) dx$ (Lebesgue integral). Show that $\lambda : \BB \to \R$ satisfies
$\lambda(\cup_n A_n) = \sum_n \lambda (A_n)$ whenever the $A_n$ are mutually
disjoint elements of $\BB$ and that $\lambda(A+t) = \lambda(A)$ for all $A \in \BB$, $t \in \R$, where $A+t :=\{a+t:~ a \in A\}$.
The function $\lambda$ is called {\sc length}.
\end{exe}

\begin{exe}
Consider a compass with a laser pointer attached at both ends of the needle.
Suppose there is an infinite screen at some
distance from the compass.
Give it a spin and see mark $X$ the location of the light with respect to
a fixed point O on the screen (positive if it is to the right of O; negative
if it is to the left). Show that $\E X$ is not defined.
(You first must translate this problem in Mathematics.)
\end{exe}

%\begin{exe}
%Consider the function $F(x):= \sum_{k \in \N} \1(x \le k)$, $x \ge 0$,
%$F(x) =0$, $x < 0$.
%Show that
%\[
%\int_\R h(x) F(dx) = \sum_{k=1}^\infty h(k),
%\]
%whenever the sum on the right makes sense.
%\end{exe}





\section{Inequalities}
%Mathematics needs inequalities probably more than equalities. Probability,
%in particular, which, in some sense, contains a lot of approximation 
%ideas needs inequalities. This section discusses some basic ones.

\subsection{Markov, Chebyshev, Chernoff}
\begin{lemma}[Markov inequality]
If $X$ is a nonnegative random variable then
\[
\Pr(X \ge t) \le \frac{\E X}{t}, \quad t > 0.
\]
\end{lemma}
\begin{proof}
We have
\[
t \1(X \ge t) \le X
\]
and $\E$ is preserved by $\le$.
\end{proof}

\begin{definition}
The variance of a real random variable $X$ with $\E X^2 < \infty$ is
defined by
\[
\var X := \E (X- \E X)^2.
\]
\end{definition}

\begin{lemma}[Chebyshev inequality]
If $X$ is a real random variable with $\E X^2 < \infty$
then
\[
\Pr(|X - \E X| \ge t) \le \frac{\var X}{t}
\]
\end{lemma}
\begin{proof}
Apply the Markov inequality to $|X - \E X|$.
\end{proof}

\begin{lemma}[Chernoff inequality]
If $X$ is a real random variable then
\[
\Pr(X \ge t) \le \frac{\E g(X)}{g(t)}
\]
where $g$ is a positive increasing function.
\end{lemma}
\begin{proof}
Since $g$ is increasing,
\[
\{X \ge t\} \subset \{g(X) \ge g(t)\}
\]
Now apply the Markov inequality to $g(X)$.
\end{proof}

\begin{exe}
Let $X$ be a discrete random variable with $\Pr (X=k) = \binom{n}{k} 2^{-k}$,
$k=0,1, \ldots,n$. Estimate $\Pr(X > na)$ for $a>0.5$ using the
above inequalities.
\end{exe}



\subsection{Jensen}
A function $\phi: \R \to \R$ is convex if
\[
\varphi(p a + (1-p) b) \le p \varphi(a) + (1-p) \varphi(b)
\]
for all $a, b \in \R$ and all $0 \le p \le 1$.
Notice that if $\xi$ is a random variable with $\Pr(\xi=a)=p$, $\Pr(\xi=b)=1-p$,
this definition can be written as
\[
\phi(\E \xi) \le \E \phi(\xi).
\]
Jensen's inequality generalises this observation:
\begin{lemma}
\label{jensen}
Let $X$ be a real integrable random variable and $\phi$ a convex function. Then
\[
\phi(\E X) \le \E \phi(X).
\] 
\end{lemma}
%Geometrically, a convex function is such that the graph of
%the function on the interval $[a, b]$ lies below the straight segment
%with endpoints $(a, \phi(a))$, $(b, \phi(b))$.
%\begin{figure}[ht]
%\centerline{\includegraphics[width=6cm]{figs/convex.eps}}
%\caption{A convex function as an an envelope of a family of straight lines}
%\end{figure}
%If we take a straight line with slope equal to the slope
%of this segment and move it down, at some point it will be entirely
%below the whole graph of $\phi$. Moreover, if we consider the set
%of all straight lines that are below the graph of $\phi$ and take
%their envelope (the maximum) then this equals $\phi$.
%Namely, 
%\begin{equation}
%\label{hb}
%\phi(x) = \max_{\ell \in L(\phi)} \ell(x), \quad x \in \R,
%\end{equation}
%where $L(\phi)$ is the collection of all functions 
%$\ell(x) \equiv \alpha x+\beta$ such that $\ell \le \phi$.
%To show this rigorously, observe that 
%\[
%a < b < c \Rightarrow
%\frac{\phi(b)-\phi(a)}{b-a}
%\le
%\frac{\phi(c)-\phi(b)}{c-b},
%\]
%by the definition of convexity.
%Let $\epsilon> 0$,  $a=b-\epsilon$, $c=b+\epsilon$
%and so
%\[
%D_-\phi(b) := \lim_{\epsilon \downarrow 0}\frac{\phi(b)-\phi(b-\epsilon)}{\epsilon}
%\le
%\lim_{\epsilon \downarrow 0}\frac{\phi(b+\epsilon)-\phi(b)}{\epsilon}:= D_+\phi(b),
%\]
%where the limits exist by monotonicity.
%Let $\alpha$ be between $D_-\phi(b)$ and $D_+\phi(b)$. Then, if $x > b+\epsilon$,
%we have
%\[
%\frac{\phi(b+\epsilon)-\phi(b)}{\epsilon}
%\le 
%\frac{\phi(x)-\phi(b)}{x-b},
%\]
%and so
%\[
%\alpha \le D_+\phi(b) \le \frac{\phi(x)-\phi(b)}{x-b}, \quad x > b,
%\]
%or $\alpha(x-b) + \phi(b) \le \phi(x)$, for all $x \ge b$. Arguing similarly 
%for all $x \le b$, we have
%\[
%\alpha(x-b) + \phi(b) \le \phi(x), \quad x \in \R.
%\]
%Thus, the function $\ell(x) := \alpha(x-b) + \phi(b) \le \phi(x)$ belongs
%to $L(\phi)$ and also, $\ell(b) = \phi(b)$.
%This proves \eqref{hb}.
%
%\noindent{\bf Proof of Lemma \ref{jensen}:}
%\[ 
%\phi(\E X) = \max_{\ell \in L(\phi)} \ell(\E X)
%=
%\max_{\ell \in L(\phi)} \E \ell(X)
%\le
%\E \max_{\ell \in L(\phi)} \ell(X)
%=
%\E \phi(X).
%\]
%The first equality is due to \eqref{hb}.
%The second uses linearity of expectation.
%The third uses monotonicity of expectation.
%The last reuses \eqref{hb}.
%$\Box$

\begin{exe}
Let $a_1, \ldots, a_n$ be positive real numbers. Define
their arithmetic, geometric and harmonic mean
by
\[
A_n=\frac{a_1+\cdots+a_n}{n},
\quad
G_n=(a_1\cdots a_n)^{1/n},
\quad
H_n = \frac{n}{a_1^{-1} + \cdots + a_n^{-1}},
\]
respectively, and show that $A_n \ge G_n \ge H_n$.
\end{exe}



\section{Moments}
\begin{definition}
When $r > 0$, the {\sc $r$-moment} of a nonnegative RV $X$ is defined as 
the quantity $\E X^r$.
The $r$-norm of a real RV $X$ is defined as $ ||X||_r:=(\E |X|^r)^{1/r}$.
\end{definition}

\begin{lemma}
\label{inorm}
The $r$-norm of $X$ is increasing in $r$.
\end{lemma}
\begin{proof}
Let $r < s$ and $\phi(x) = x^{s/r}$, $x > 0$. Notice that $\phi$
is convex. (This follows from the fact that its second derivative is positive.)
Now apply the Jensen inequality.
\end{proof}

\begin{corollary}
If $\E |X|^p < \infty$ for some $p > 0$ then $\E |X|^r < \infty$ for
all $0 < r < p$.
\end{corollary}




\section{H\"older, Minkowski and Cauchy-Bunyakowskii-Schwarz}

\begin{definition}
If $X, Y$ are real random variables on the same $(\Omega, \FF, \Pr)$,
the quantity $\E(X Y)$ (whenever it is defined) is called {\sc correlation}
between $X$ and $Y$. 
The quantity $\cov(X,Y):= \E((X-\E X) (Y-\E Y))$ is called {\sc covariance}
between $X$ and $Y$.
\end{definition}

\begin{lemma}[H\"older inequality]
Let $X, Y$ be real random variables. Then
\[
|\E(XY)| \le ||X||_p ||Y||_q,
\]
for any $p, q > 0$, $p^{-1} + q^{-1} =1$, as long as all 
terms involved exist and are finite.
\end{lemma}
\begin{proof}
Let $(\Omega, \FF, \Pr)$ be a probability space on which
both $X, Y$ are defined. Without loss of generality
assume that they are both nonnegative. Let $q > 1$ and assume that
$\E (Y^q) < \infty$. Consider the probability
\[
\Pr_q(A) := \frac{\E(Y^q \1_A)}{\E(Y^q)}, \quad A \in \FF.
\]
Let $\E_q$ denote expectation with respect to $\Pr_q$.
Therefore, for any nonnegative random variable $W:(\Omega, \FF) \to (\R, \BB)$,
\begin{equation}
\label{WWW}
\E_q W = \frac{\E(Y^q W)}{\E (Y^q)}.
\end{equation}
Letting, in \eqref{WWW}, $W = XY^{1-q}$, we obtain
\[
\E(XY) = \E(Y^q)~ \E_q(XY^{1-q}).
\]
Let $p$ be defined from $p^{-1} + q^{-1} =1$. Necessarily, $p > 1$.
{From} Lemma \ref{inorm} we have
\[
\E_q Z \le (\E_q Z^p)^{1/p},
\]
for any nonnegative
random variable $Z :(\Omega, \FF) \to (\R, \BB)$ with 
$\E Z^p < \infty$.
Therefore,
\begin{align*}
\E(XY) &\le \E(Y^q) ~ (\E_q ((XY^{1-q})^p))^{1/p}
\\
&= \E(Y^q) ~ \left(\frac{\E (X^p Y^q Y^{(1-q)p})}{\E (Y^q)}\right)^{1/p}
\\
&= (\E(Y^q))^{1-1/p} ~ (\E (X^p Y^{q+(1-q)p}))^{1/p}.
\end{align*}
Since $1-1/p = 1/q$ and $q+(1-q)p=0$, the result follows.
\end{proof}



\begin{corollary}{\bf(Cauchy-Bunyakowskii-Schwarz)}
Let $X, Y$ be real random variables. Then
\[
|\E(XY)| \le ||X||_2 ||Y||_2,
\]
as long as all
terms involved exist and are finite.
\end{corollary}
\begin{proof}
Notice that $\tfrac{1}{2}+\tfrac{1}{2}=1$ and apply H\"older.
\end{proof}

\begin{corollary}Let $X, Y$ be real random variables. Let 
\[
\rho(X, Y) := \cov(X,Y) /\sqrt{\var(X)} \sqrt{\var(Y)},
\]
whenever the terms exist.
Then
\[
-1 \le \rho(X,Y) \le 1.
\]
\end{corollary}




\begin{lemma}[Minkowski inequality]
Let $X, Y$ be real random variables. Then
\[
||X+Y ||_p \le ||X||_p + ||Y||_p,
\]
for any $p > 1$, as long as all
terms involved exist and are finite.
\end{lemma}
\begin{proof}
Use the H\"older inequality as follows:
\begin{align*}
\E(|X+Y|^p)
& = \E(|X|~|X+Y|^{p-1}) + \E(|Y|~|X+Y|^{p-1})
\\
&\le [\E(|X|^p)]^{1/p} ~ [\E(|X+Y|^{(p-1)q})]^{1/q}
+[\E(|Y|^p)]^{1/p} ~ [\E(|X+Y|^{(p-1)q})]^{1/q}
\\
&= (||X||_p + ||Y||_p) ~ [\E(|X+Y|^p)]^{1/q},
\end{align*}
\end{proof}



\section{Moment generating functions}
Let $X$ be a real random variable. Since, for any $\theta \in \R$,
the random variable $e^{\theta X}$ is nonnegative, its expectation
exists (but may be equal to $+\infty$). We define the function
$M : \R \to \R\cup\{+\infty\}$ by
\[
M(\theta) := \E(e^{\theta X}), \quad \theta \in \R.
\]
Notice that $M(0) =1$.
This function is useful if $M(\theta) < \infty$ for some $\theta \not = 0$.
(Indeed, there are cases where $\theta=0$ is the only point at which
$M$ is finite.)
If $X$ is a positive random variable, then $M(\theta) < \infty$ for all 
$\theta \le 0$.
If $X$ is a negative random variable, then $M(\theta) < \infty$ for all 
$\theta \ge 0$.
$M$ depends only on the law of $X$. Indeed, using the Substitution Rule
(Lemma \ref{subst}) we can write
\[
M(\theta) = \E_{\Pr_X} (e^{\theta \iota}),
\quad
\text{where } \iota(x) \equiv x,
\]
and, if $X$ has absolutely continuous distribution function $F$ with density
$f$, we can write
\[
M(\theta) = \int_{\R} e^{\theta x} f(x) dx \quad \text{ (Lebesgue integral) }.
\]
The function $M$ is called {\sc moment generating function} because
of the following:
\begin{lemma}
\label{mmm}
Suppose there exist $a < 0 < b$ such that $M(\theta) < \infty$ for
all $a < \theta < b$. Then 
\\
(i) the $r$-moment of $X$ exists for all $r \in \N$
and is given by the $r$-derivative of $M$ at $0$:
\[
\E(X^r) = D^r M(0).
\]
(ii) 
\[
M(\theta) = \sum_{r=0}^\infty \frac{\E(X^r)}{r!} \theta^r,
\quad a < \theta < b.
\]
(iii) There is only one distribution function $F$ such that
if $X$ has distribution function $F$ then it has moment generating function 
$M$.
\end{lemma}
\begin{proof} [sketch]
Using the Dominated Convergence Theorem \ref{dct}, we can see that $M$ is
infinitely differentiable at $0$ with $r$-derivative equal to the
$r$-moment of $X$. Moreover, we can see that $M$ is a real
analytic function around $0$. Hence Taylor's theorem holds,
which yields the second claim.
\end{proof}
%To talk intelligently about moment generating functions we must
%talk about Laplace and Fourier transforms.
\begin{exe}
\label{cochy}
Let $X$ be absolutely continuous with density $f(x) = \pi^{-1} (1+x^2)^{-1}$,
$x \in \R$. Show that the moment generating function $M(\theta)$ is only
defined for $\theta=0$.
\end{exe}
 

\section{Characteristic functions}
Moment generating functions, as the last exercise shows, may not give
any information at all. There is an analytic technique bypassing this
problem, consisting of replacing the argument of the moment generating function
by an imaginary number, i.e.\ a number of the form $i t$, where $i = \sqrt{-1}$.
First, we define the expectation of a {\sc complex  random variable}
$X_1 + i X_2$, where $X_1, X_2$ are real random variables, by
\[
\E(X_1 + i X_2) := \E X_1 + i \E X_2,
\]
and observe that 
\begin{equation*}
|\E X | \le \E |X|.
\end{equation*}
We then define the {\sc characteristic function} of $X$ by
\[
\phi(t) := \E e^{i t X}, \quad t \in \R.
\]
By Taylor-expansion of the exponential function we can see that
\[
e^{itX} = \cos(tX) + i \sin(tX).
\]
So $|e^{itX}| = \cos(tX)^2 + \sin(tX)^2| = 1$, and therefore
$\phi(t)$ is defined for all $t$ and $|\phi(t)| \le 1$.
\begin{theorem}
Let $\phi$ be the characteristic function of a random variable with
distribution function $F$.
Suppose that a random variable $Y$ has characteristic function $\phi$.
Then $Y$ has distribution function $F$.
\end{theorem}
In other words, the charateristic function uniquely determines (characterises)
the law of a random variable.
It can be shown that:\\
1. $\phi$ is continuous (and, in fact, analytic) function.\\
2. The complex conjugate $\phi(t)$ is $\phi(-t)$. If $X$ is
symmetric around $0$ (i.e.\ $-X$ has the same law as $X$) then
$\phi(t)$ is a real number.\\
3. It is a positive-semidefinite function, i.e.\ for every
$n \in \N$, for every $a_1, \ldots, a_n \in \C$, and every
$t_1, \ldots, t_n \in \R$, we have
\[
\sum_{k=1}^n\sum_{\ell=1}^n a_k \overline{a_\ell} \phi(t_k-t_\ell) \ge 0.
\]
This property says that if we form the $n \times n$ matrix
with entries $\phi(t_k-t_\ell)$, then this matrix has nonnegative
eigenvalues.

If a random variable $X$ is absolutely continuous with density $f$, then
its characteristic function is given by
\[
\phi(t) = \int_{-\infty}^\infty e^{itx} f(x) dx.
\]
This is the {\sc Fourier transform} of $f$. The inverse Fourier 
transform determines $f$ from $\phi$:
\[
f(x) = \frac{1}{\pi} \int_{-\infty}^\infty e^{-itx} \phi(t) dt.
\]
\begin{exe}
Show that the random variable of Exercise \ref{cochy} has characteristic 
function $\phi(t) = e^{-|t|}$.
\end{exe}






%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\noindent
\hrulefill

\begin{thebibliography}{9}
\bibitem{fg}
{\sc B. Fristedt \& L. Gray},
{\em A Modern Approach to Probability Theory},
Birkh\"auser, 1997.
\bibitem{hs}
{\sc E. Hewitt \& K. Stromberg},
{\em Real and Abstract Analysis},
Springer, 1965.
%\bibitem{kf}
%{\sc A. N. Kolmogorov \& S. V. Fomin}, 
%{\em Introductory Real Analysis}, 
%Dover, 1975.
\bibitem{k}
{\sc T. Konstantopoulos},
Extended set of lecture notes, with proofs,\\
{\tt www.ma.hw.ac.uk/$\sim$takis}
%\bibitem{dm}
%{\sc D. Mumford},
%The dawning of the age of stochasticity.\\
%{\tt http://www.dam.brown.edu/people/mumford/Papers/Dawning.pdf}, 1999.
\bibitem{wil}
{\sc D. Williams},
{\em Probability with Martingales},
Cambridge, 1991.
\end{thebibliography}

\end{unit}

\end{document}
